1. Field of the Invention
The present invention relates to direct access block memory storage devices, and, in particular, to command tracking and conflict checking for solid state disks (SSDs).
2. Description of the Related Art
Flash memory is a type of non-volatile memory that is electrically erasable and re-programmable. Flash memory is primarily used in memory cards and USB flash drives for general storage and transfer of data between computers and other digital products. Flash memory is a specific type of electrically erasable programmable read-only memory (EEPROM) that is programmed and erased in large blocks. One commonly employed type of flash memory technology is NAND flash memory. NAND flash memory forms the core of the flash memory available today, especially for removable universal serial bus (USB) storage devices known as USB flash drives, as well as most memory cards. NAND flash memory exhibits fast erase and write times, requires small chip area per cell, and has high endurance. However, the I/O interface of NAND flash memory does not provide full address and data bus capability and, thus, generally does not allow random access to memory locations.
There are three basic operations for NAND devices: read, write and erase. The read and write operations are performed on a page by page basis. Page sizes are generally 2N bytes, where N is an integer, with typical page sizes of, for example, 2,048 bytes (2 kb), 4,096 bytes (4 kb), 8,192 bytes (8 kb) or more per page. Pages are typically arranged in blocks, and an erase operation is performed on a block by block basis. Typical block sizes are, for example, 64 or 128 pages per block. Pages must be written sequentially, usually from a low address to a high address. Lower addresses cannot be rewritten until the block is erased.
A hard disk is addressed linearly by logical block address (LBA). A hard disk write operation provides new data to be written to a given LBA. Old data is over-written by new data at the same physical LBA. NAND flash memories are accessed analogously to block devices, such as hard disks. NAND devices address memory linearly by page number. However, each page might generally be written only once since a NAND device requires that a block of data be erased before new data is written to the block. Thus, for a NAND device to write new data to a given LBA, the new data is written to an erased page that is a different physical page than the page previously used for that LBA. Therefore, NAND devices require device driver software, or a separate controller chip with firmware, to maintain a record of mappings of each LBA to the current page number where its data is stored. This record mapping is typically managed by a flash translation layer (FTL) in software that might generate a logical-to-physical translation table. The flash translation layer corresponds to the media layer of software and/or firmware controlling an HDD.
Since an HDD or SSD might receive one or more commands such as read, write or erase operations, before a previously received command has completed, a queue might generally maintain a list of commands received while a previous command is being processed. In storage devices operating in accordance with the Small Computer System Interface (SCSI) standard, a control field, such as the SCSI Queue Algorithm Modifier (QAM) field, might be employed to indicate whether reordering of the queue of received commands is permitted. For example, the SCSI Primary Commands specification (SPC-3, Section 7.4.6, pg. 285, 2005, included by reference herein) defines the QAM field. As defined, when the QAM field has a value of zero, command reordering is restricted, and queued commands must be processed in the order in which they are received. When the QAM field has a value of one, command reordering is permitted, and the storage device may process queued commands in any order.
When commands are received, an HDD or SSD might generally perform conflict checking between the received command and any outstanding or queued commands. One solution is to track commands by adding every received command to a linked list. The linked list is searched for conflicts every time a new command is received. Although easy to implement and generally not requiring much memory space, adding every command to a linked list can require a long execution search time when the list of commands is long.
Another solution is to add received commands to a balanced binary tree, sorted by the starting LBA of the command (the search key). A binary tree is a tree data structure in which each parent node has at most two children or subtrees (left and right). Binary trees are commonly implemented with the left subtree of a node containing nodes with search keys less than the parent node's key, and the right subtree of a node containing nodes with search keys greater than the parent node's key. A balanced binary tree is a binary tree where all branches have a predictable depth that can differ by no more than one. The depth of a binary tree is equal to the integer value of log2(n), where n is the number of nodes of the tree.
A balanced binary tree can require a large amount of code memory space because it is a relatively complex data structure to maintain. Further, long execution time might be required to add or remove commands from the data structure due to the complex nature of a balanced binary tree. Searches might require long execution time due to the added complexity that commands generally affect ranges of LBAs, not just the starting LBA (i.e. the search key). Therefore, there is a need for command tracking and conflict checking that is easy to implement, does not require much memory space, and provides fast execution time.